package com.jz;

import com.future.util.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * Description: JZ68 二叉搜索树的最近公共祖先
 *
 * @author weiruibai.vendor
 * Date: 2022/9/29 10:09
 */
public class JZ68 {

    public static void main(String[] args) {
        JZ68 jz68 = new JZ68();
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(1);
        root.right = new TreeNode(12);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(11);
        root.right.right = new TreeNode(14);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        //int p = 1, q = 12;
        int p = 11, q = 12;
        System.out.println(jz68.lowestCommonAncestor(root, p, q));

    }

    /**
     * {7,1,12,0,4,11,14,#,#,3,5},1,12
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public int lowestCommonAncestor(TreeNode root, int p, int q) {

        Map<Integer, TreeNode> childParent = new HashMap<Integer, TreeNode>();
        LinkedList<TreeNode> linked = new LinkedList<TreeNode>();
        linked.add(root);
        childParent.put(root.val, root);
        while (!linked.isEmpty()) {
            TreeNode curNode = linked.poll();
            if (curNode.left != null) {
                childParent.put(curNode.left.val, curNode);
                linked.add(curNode.left);
            }
            if (curNode.right != null) {
                childParent.put(curNode.right.val, curNode);
                linked.add(curNode.right);
            }
        }
        Set<Integer> set = new HashSet<>();
        set.add(p);
        while (childParent.get(p) != root) {
            p = childParent.get(p).val;
            set.add(p);
        }
        set.add(root.val);// 一定要加
        while (!set.contains(q)) {
            q = childParent.get(q).val;
        }
        return q;
    }
}
